The present invention relates to a method of modeling an intended object's three-dimensional surface and more particularly to a method of generating and employing a two-dimensional slice from a cross-section of a three-dimensional tesselated model of the intended object's three-dimensional surface.
The advent of Solid Freeform Fabrication (SFF) technologies (a.k.a. Rapid Prototyping technologies) has reduced the cycle time for prototyping. Typically, an SFF process starts with a solid model of an intended object, such as a part to be machined for example, in a Computer-Aided Design (CAD) system. The model of the intended object in the CAD system is then converted into a computer file in the stereolithographic (STL) format. The STL file defines the three-dimensional exterior surface of the intended object in a tesselated form as: (1) a plurality of flat planar sections known as facets and (2) the outward pointing normals to these planar sections.
In general, a "facet model" represents a three-dimensional surface of an intended object by spatial boundaries, which are defined by a set of planar faces. The facet model is a special case of the more general boundary representation, which does not require the boundaries of the object to be planar. The term "facet" can be considered to denote a planar region being used to define a model boundary wherein the outline of the planar region is defined by any polygonal shape. However, in the Solid Freeform Fabrication (SFF) community, the term "facet" is typically understood to have an outline shaped as a triangle, and that is the understanding followed in the present application.
In a typical Rapid Prototyping (RP) application for an STL file, the faceted representation of the intended object is processed by a so-called "slicing engine," which produces a two dimensional representation of the cross-section of the intended object. The slicing engine provides the two-dimensional representation in the form of 2-D layers (a.k.a. slices). Each layer is bounded top and bottom by a so-called "slicing plane," and the edge of the layer disposed between the top and bottom slicing planes represents to a varying degree of accuracy, the commensurate cross-section of the surface of the intended object. The intended object is then "built" by stacking these layers one on top of the other layer-by-layer from bottom to top. Some slicing engines have difficulty dealing with certain key characteristics in the surface of the intended object and sudden changes in the complexity of the surface of the intended object. Moreover, providing the slicing engine with a data file in the Stereolithographic format (an STL file) as the input, negatively impacts the performance of the slicing engine in rapid prototyping systems.
As shown in FIGS. 1A-1C, a typical CAD software package (e.g., 3-D Systems, 1988) models a solid object, such as a sphere, as a set of triangular facets. Unfortunately, the typical CAD package independently stores the data representing each of these facets, as if each facet were created and tossed into a bucket with no particular ordering and without information relating a given facet to any other facet in the bucket.
In stereolithography, about 60% of the total time spent preparing the model is devoted to generating the slice data, i.e., slicing. Moreover, far more of the time devoted to slicing is consumed by searching for the facets that will have an intersection with a particular slice plane, than is consumed in performing the plane-facet intersection calculations required to generate the slice data.
To reduce the time required to generate the slice data, sorting of triangles is recommended by 3-D Systems. However, this does not fully alleviate the problem because triangle sorting is uni-directional, either descending or ascending. The benefits of sorting are often diminished because of the sheer complexity of the model and because there are too many variations in the sizes of triangles.
Moreover, under certain circumstances such as shown in an E-shaped block in FIG. 2, sorting may even increase the computation time. Ignoring the front and rear faces of the block for the sake of convenience, each of the 12 faces F.sub.1 through F.sub.12 of the block will be represented in the STL format by at least two triangular facets. When the faces of the block are sorted in ascending order, with the minimum Z coordinate (Z-min) of each facet F.sub.i as the sorting criterion, faces of the block will be ordered in the following First Sequence: F.sub.1, F.sub.2, F.sub.3, F.sub.4, F.sub.5, F.sub.6, F.sub.7, F.sub.8, F.sub.9, F.sub.10, F.sub.11, F.sub.12. In this FIG. 2 example, only faces F.sub.2 and F.sub.11 intersect the slice plane A--A. Since these two faces are separated by eight other faces (assuming that each face is composed of two facets in the STL format), sixteen failed searches will occur before the correct facets that intersect the slice plane A--A can be found. If the sorting criterion is changed to the maximum Z coordinate (Z-max) of each facet, then this Second Sequence will be given by: F.sub.1, F.sub.3, F.sub.4, F.sub.5, F.sub.6, F.sub.7, F.sub.8, F.sub.9, F.sub.10, F.sub.11, F.sub.2, F.sub.12. The Second Sequence is the same as the First Sequence except for the new position of F.sub.2. Since slice plane B--B intersects only facets F.sub.2 and F.sub.3 in the FIG. 2 example, there will be again sixteen failed searches. As is evident from this example, as the complexity of the STL model increases, the computational cost of searching for facets that intersect the slice plane, quickly becomes prohibitive.
In addition, STL files contain a significant amount of redundant information, which can waste processing time. For example, vertex coordinates are stated explicitly for each facet. Since a vertex is always shared by a minimum of three facets, this results in each vertex being stored in the STL file data at least three times.
As shown in FIGS. 1A-1C, another of the limitations of an STL file is its inability to represent curved surfaces accurately. This results from the unavoidable error that arises whenever a three-dimensional surface of an object featuring curved surfaces is approximated by planar triangular facets. As illustrated in FIG. 1, choosing smaller and smaller triangles can reduce the error, but cannot eliminate the error.
In a 1991 article, Chalasani et al, have proposed two approaches for layered modeling of 3-D objects. In the first approach, each of the slice planes defining the layers is determined as the geometric intersection between the intended object and a plane horizontal to the platform of a stereolithography apparatus. Each facet that intersects the slice plane will form a directed line segment (vector) on the slice plane. Since intersections are not found in any particular order, the vectors must be sorted in head-to-tail fashion in order to derive a closed contour on that slice plane. This makes the process slow and inefficient.
Chalasani et al's second approach uses a scan-line-type search to find an intersection between the slice plane and a facet, and the search starts at the global origin. When the search point reaches the boundary of the faceted intended object for the first time since the search began, the first intersection is recorded. This first intersection will trigger a contour-tracing procedure in which the "search point becomes a draw point" and follows the plane of the facet until it reaches another edge. An adjacency list is consulted for the facet that shares this second edge of the first facet. Then the draw point will move along the plane of this facet. The process is repeated until the draw point comes back to the first intersection.
However, because Chalasani et al's methods produce many failed searches before an intersection (match) is found, it is slow. It is not clear how Chalasani et al's search point is incremented. Also, apart from stating that the layer thickness should be varied according to the local curvature of the object, Chalasani et al fails to demonstrate or suggest how this can be achieved.
In a December 1992 article, Vouzelaud and Bagchi reported their use of slices to obtain 2-D contours from a 3-D CAD model in a way that varies the slice thickness to better represent the surface of the intended object. A user defined "Quality Index," , which is the maximum peak to valley height of the profile in the assessment length, was used by Loney and Ozsoy (1987) to calculate the side step or step size for parametric cubic patches and therefore yield a constant surface attribute. However, by obtaining the 2-D contours from the CAD systems themselves, Vouzelaud and Bagchi eliminated the need to have an STL file and the limitations associated with the STL file. Also, unlike the contours obtained from the tesselated model represented by the STL file, the contours obtained from the CAD system are more accurate representations of the original model. Despite their limitations, STL files are widely used by the Rapid Prototyping industry because of the easy availability of STL translators and the simplicity of the STL format.
In a 1993 article, Dolenc and Makela suggested implementing back-tracking as part of a procedure for varying the thickness of the layers used to represent different portions of the surface of the intended object. However, the details of their implementation are not known, and the robustness of their back-tracking procedure is suspect.